#include <stdio.h>
#include <windows.h>
#include <malloc.h>

#define TRUE 1
#define FALSE 0

#define ELEM_INITIAL 0 

	typedef int elemType;
	typedef struct LNode{
		elemType data;
		LNode* next;
	}LNode;
	
	int _error(char* msg)
	{
		printf("%s\n",msg);
		system("pause");
		exit(FALSE);
		return 0;
	}
	
	int InitList(LNode** L)
	{
		*L = (LNode*) malloc(sizeof LNode);
		if (*L == NULL) _error("Application of memory failure.");

		(*L)->data = ELEM_INITIAL;
		(*L)->next = NULL;
		
		return TRUE;
	}

	int ListNone(LNode* L)
	{
		if (L == NULL) return TRUE;
		else return FALSE;
	}
	
	int ListLength(LNode* L)
	{
		int len = 0;

		while(L)
		{
			len++;
			L = L->next;
		}

		return len;
	}

	int ClearList(LNode* L)
	{
		LNode* P = L->next, *Q = L->next;
		L->data = ELEM_INITIAL;
		L->next = NULL;

		while(P)
		{
			P = Q->next;
			free(Q);
			Q = P;
		}

		return TRUE;
	}

	int DestoryList(LNode* L)
	{
		ClearList(L);

		free(L);
		L = NULL;

		return TRUE;
	}
	
	int ListEmpty(LNode* L)
	{
		if (ListNone(L)) _error("Link list not exist.");

		if (!L->next && L->data == ELEM_INITIAL) return TRUE;
		else return FALSE;
	}

	int GetElem(LNode* L, int i, elemType* e)
	{
		int len = ListLength(L);

		if (i<=0 || i>len) _error("The second parameter 'position' bounds, or list is empty.");

		while(--i)
		{
			L = L->next;
		}

		*e = L->data;

		return TRUE;
	}

	int _equl(elemType m, elemType n)
	{
		return m == n ? TRUE : FALSE;
	}

	int LocateElem(LNode* L, elemType e, int (*compare)(elemType, elemType) = _equl)
	{
		int pos = 0;

		while(L)
		{
			if (compare(L->data, e)) return ++pos;
			L = L->next;
			pos++;
		}

		return FALSE;
	}

	int PriorElem(LNode* L, elemType curE, elemType* preE)
	{
		int pos = LocateElem(L, curE);

		if (pos == 0 || pos == 1)
			_error("Element no found in list, or the element you given is first in the list.");

		pos--;

		while(--pos)
		{
			L = L->next;
		}

		*preE = L->data;

		return TRUE;
	}

	int NextElem(LNode* L, elemType curE, elemType* nextE)
	{
		int pos = LocateElem(L, curE);

		if (pos == 0 || pos == ListLength(L))
			_error("Element no found in list, or the element you given is the last in the list.");

		while(pos--)
		{
			L = L->next;
		}

		*nextE = L->data;

		return TRUE;
	}

	int ListInsert(LNode* L, int i,elemType e)
	{
		LNode *P;

		if (ListEmpty(L))
		{
			L->data = e;
			return TRUE;
		}

		i--;

		while(--i && L->next)
		{
			L = L->next;
		}

		P = (LNode*) malloc(sizeof LNode);
		if (P == NULL) _error("Application of memory failure.");

		P -> data = e;

		P->next = L->next;
		L->next = P;

		return TRUE;
	}

	int ListDelete(LNode* L, int i,elemType* e)
	{
		LNode* P;
		i--;

		while(--i)
		{
			L = L->next;
		}

		*e = L->next->data;

		P = L->next->next;
		free(L->next);
		L->next = P;

		return TRUE;
	}

	int _show(elemType* e)
	{
		printf("value:\t%d\n",*e);

		return TRUE;
	}

	int ListTraverse(LNode* L, int (*visit)(elemType*) = _show)
	{
		while(L)
		{
			visit(&L->data);
			L = L->next;
		}
		
		return TRUE;
	}

	int main()
	{
		LNode* examL;
		elemType examE;
		
		InitList(&examL);
		
		if (ListEmpty(examL)) printf("Now, list is empty, and we will insert data into it!\n");

		ListInsert(examL, 9, 11);
		ListInsert(examL, 9, 12);
		ListInsert(examL, 9, 13);
		ListInsert(examL, 9, 14);
		ListInsert(examL, 9, 15);
		ListInsert(examL, 9, 16);

		printf("We destory the list and then reset it.\n");

		DestoryList(examL);
		InitList(&examL);

		ListInsert(examL, 9, 11);
		ListInsert(examL, 9, 12);
		ListInsert(examL, 9, 13);
		ListInsert(examL, 9, 14);
		ListInsert(examL, 9, 15);
		ListInsert(examL, 9, 16);

		ListTraverse(examL);
		printf("\nTotal ength:%d\n\n",ListLength(examL));

		printf("next, clear the list.See it again.\n");
		ClearList(examL);

		ListTraverse(examL);
		printf("\nTotal length:%d\n\n",ListLength(examL));

		printf("insert data again\n");
		ListInsert(examL, 9, 11);
		ListInsert(examL, 9, 12);
		ListInsert(examL, 9, 13);
		ListInsert(examL, 9, 14);
		ListInsert(examL, 9, 15);
		ListInsert(examL, 9, 16);

		ListTraverse(examL);
		printf("\nTotal ength:%d\n\n",ListLength(examL));

		GetElem(examL, 3, &examE);
		printf("elem 3 value:%d\n",examE);

		printf("Show where '12' is:%d\n",LocateElem(examL, 12));
		
		NextElem(examL, 12, &examE);
		printf("Show element next '12':%d\n",examE);

		PriorElem(examL, 12, &examE);
		printf("Show element before '12':%d\n",examE);

		ListInsert(examL, 3, 10);
		printf("Put the '10' as third element, show new list:\n");
		ListTraverse(examL);
		printf("\nTotal ength:%d\n\n",ListLength(examL));

		ListDelete(examL, 3, &examE);
		printf("Delete value '10' now, who is delete:%d\nshow again:\n",examE);
		ListTraverse(examL);
		printf("\nTotal ength:%d\n\n",ListLength(examL));
		
		system("pause");
		return 0;
	}